package com.hh.test.sort;

import com.hh.test.util.PrintUtil;
import com.hh.test.util.ScannerUtil;

public class QuickSort implements Sort {

	public static void main(String[] args) {
		Integer[] array=new Integer[] {14,23,33,12,23,13,12,321,34,123,13,21432,3,5345,6,435,345,2,34,3,2};
//		Integer[] array=new Integer[] {5,1,2,34,3,2};
//		Integer[] array = ScannerUtil.getIntArrayInput();
		PrintUtil.print(array);
		new QuickSort().sort(array);
		PrintUtil.print(array);
	}

	@Override
	public void sort(Integer[] array) {

		sort(array, 0, array.length - 1);

	}

	/**
	 * 0 1 2 3 4
	 * 
	 * @param array
	 * @param st
	 * @param et
	 */
	public void sort(Integer[] array, int st, int et) {
		int stt = st, ett = et;
		int bz = array[st];
		
		for (int i = stt + 1; i <= ett; i++) {
			if (et - i == -1) {
				break;
			}
			if (bz > array[i]) {
				swap(array, i, et);
				et--;
				i--;
			}
		}
		swap(array, stt, et);
		PrintUtil.print(array);
		if (et - 1 > stt)
			sort(array, stt, et - 1);
		if (ett > et + 1)
			sort(array, et + 1, ett);

	}

	void swap(Integer[] array, int i, int j) {
		int temp = array[i];
		array[i] = array[j];
		array[j] = temp;
	}

}
